“Ubiquitous” is a buzz word in recent years. The word “ubiquitous” means an information system which allows it to use computers and network to, for example, acquire the status of a person or an object so as to monitor the overall situation of the place, or provide information pertinent to the circumstances.
What plays an important role in the ubiquitous is a sensor network. The sensor network is a system that employs the idea in which respective sensors incorporate miniature wireless devices therein, and the sensors autonomously circulate information with each other by air, so as to provide services which are suited for the location based on the collected data.
Applications for the sensor network include the fields such as disaster prevention, prevention of crimes, security, medical service, environment issue, and agriculture. The applications also include the fields such as the control of office air conditioner, coordination between a vehicle and information about roads or between vehicles with the sensor network mounted in an on-vehicle computer.
There are various kinds of sensors which include: in addition to those in common use which sense heat, temperature, moisture, humidity, sound, light, magnetism, wind, vibration, pressure, acceleration, and orientation; bio-sensors which measure such vital signs as blood pressure, pulsation, heartbeat, and blood sugar; and those which detect substances such as toxic compounds or rare useful resources. Combining these sensors enables it to gather vast kinds of information and provide various applications.
The applications encompass various fields, and information about the housing life of human being, human behavior, and bionomical information that provides ailments of human being can be transmitted, thus making it crucial to protect the privacy when transmitting such pieces of information.
Moreover, the transmitters must be extremely low in manufacturing cost, if they are to be mounted on various sensors.
Among those that can provide transmission at low costs is one called RFID. The RFID is provided in a tiny wireless chip and is used to provide the mechanism for the identification and management of individual persons or goods. However, no consideration has been paid to the protection of privacy.
One of methods addressing this problem employs a hash chain which provides the method for assigning a terminal ID that identifies a terminal within a network environment and undergoes dynamic changes for the purpose of security.
In a scheme that employs the hash chain (refer to non-patent document 1), for example, a value S(k, 0) shared by an RFID tag which is uniquely identified by number k and by a server of the network (NW) is hashed i times with a hash function H to determine S(k, i), and a(k, i) obtained by hashing S(k, i) with a hash function J (hash function G in non-patent document 1) is used as the i-th tag ID. The above calculation is done first by the tag, and the tag ID is sent to NW. A server in the NW calculates a(k, i) for all the accommodated tags and creates a correspondence table between a(k, i) and k in advance, and looks for the value of k corresponding to a(k, i) which agrees with a(k, i) that was sent from the tag, thereby to uniquely identify the tag of number k.
This scheme has such a feature that deleting the information of S(k, 0) and S(k, i−1) from a memory at the tag makes it difficult to infer the value of a(k, i−1) from the value of a(k, 0) of the past, even if S(k, i) can be obtained from the discarded tag. This feature takes advantage of the fact that inverse calculation is difficult for hash function H. Moreover, because inverse calculation is difficult for hash function J, it is also difficult to infer the value of S(k, i) from the value of a(k, i) that has been sent out, thus it is difficult to infer a(k, i+1) which is used next.
As a result, privacy of the tag's owner can be protected as it is difficult to track the tag by analyzing the tag's memory content or by eavesdropping the wireless communication.
Meanwhile, in the challenge & response authentication scheme, which is one of authentication schemes employed in ubiquitous networking, a server can authenticate a client without need to exchange a secret value held (shared) in advance by the server and the client (non-patent documents 2 and 3).
In the challenge & response authentication scheme, the server sends to the client a value called the challenge (for example, a random number RA described in page 55 of non-patent document 3) which varies every time. Here, a random number is generally used in the method for generating the value which varies every time.
Then, the client carries out calculation by combining the challenge and the secret value (for example, calculation using MAC (message authentication code) described in page 55 of non-patent document 3), and sends the result in a response (Hk described in page 55 of non-patent document 3) to the server. Last, the server carries out the calculation by combining the challenge and the secret value similarly to the client and compares the result of calculation of the server itself with the response received from the client. When it is determined that both values agree, the server authenticates the client as a legitimate client with which the server shares the secret value. In the case of mutual authentication, authentication is repeated by switching the roles of the server and the client. It should be noted that non-patent document 2 discloses a technology similar to that of non-patent document 3, except for the fact that the client in non-patent document 3 generates a random number RB and generates a response using this random number RB.
Thus in the challenge & response authentication scheme, the server and the client communicate a value which changes every time through a communication channel therebetween, and hence it is impossible for an eavesdropper who does not know the secret value shared in advance by the server and the client to pretend to be the client.    Non-patent document 1: Forward-Secure RFID Privacy Protection for Low-cost RFID: Miyako Ohkubo, Koutarou Suzuki, Shingo Kinoshita (NTT), CSS2003, pp. 491-496, October 2003    Non-patent document 2: Future Network Series, “Ubiquitous service network technology”, Isao Miyake, Hiroshi Saito, Hideaki Yumiba; ISBN 4885499186, pp. 228-229; September 2003    Non-patent document 3: Applied Cryptography, Second Edition, Bruce Schneier, John Wiley & Sons, ISBN 0-471-11709-9, pp. 52-57 and 454-459; 1996